package pers.whj.util.list;

import pers.whj.util.InvalidParamException;
import pers.whj.util.NoSuchElementException;
import pers.whj.util.sort.Sort;

import java.lang.reflect.Array;

public class LinkedList<T> implements List<T>, ListOp<T> {
    private int mLength;
    private final Node<T> mHead;
    private final Node<T> mTail;

    public LinkedList() {
        mLength = 0;
        mHead = new Node<>(null, null, null);
        mTail = new Node<>(null, mHead, null);
        mHead.next = mTail;
    }

    @Override
    public int length() {
        return mLength;
    }

    @Override
    public boolean contains(Object data) {
        return find(data) != -1;
    }

    @Override
    public int find(Object data) {
        int index = 0;
        if (data == null) {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (x.data == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (data.equals(x.data)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    @Override
    public int findFromLast(Object data) {
        int index = mLength - 1;
        if (data == null) {
            for (Node<T> x = mTail.pre; x != mHead; x = x.pre) {
                if (x.data == null) {
                    return index;
                }
                index--;
            }
        } else {
            for (Node<T> x = mTail.pre; x != mHead; x = x.pre) {
                if (data.equals(x.data)) {
                    return index;
                }
                index--;
            }
        }
        return -1;
    }

    @Override
    public int find(Object data, int start, int end) {
        checkIndexOfRange(start, end);
        int index = start;
        Node<T> x = node(start);
        if (data == null) {
            for (; x != mTail; x = x.next) {
                if (x.data == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (; x != mTail; x = x.next) {
                if (data.equals(x.data)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    @Override
    public int count(Object data) {
        int counts = 0;
        if (data == null) {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (x.data == null) {
                    counts++;
                }
            }
        } else {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (data.equals(x.data)) {
                    counts++;
                }
            }
        }
        return counts;
    }

    @Override
    public T get(int index) {
        checkIndex(index);
        return node(index).data;
    }

    @Override
    public T getHead() {
        checkIfElementExists(0);
        return mHead.next.data;
    }

    @Override
    public T getTail() {
        checkIfElementExists(mLength - 1);
        return mTail.pre.data;
    }

    @Override
    public T set(int index, T data) {
        checkIndex(index);
        Node<T> node = node(index);
        T oldData = node.data;
        node.data = data;
        return oldData;
    }

    @Override
    public T setHead(T data) {
        checkIfElementExists(0);
        T oldData = mHead.next.data;
        mHead.next.data = data;
        return oldData;
    }

    @Override
    public T setTail(T data) {
        checkIfElementExists(mLength - 1);
        T oldData = mTail.pre.data;
        mTail.pre.data = data;
        return oldData;
    }

    @Override
    public void setAll(T data) {
        for (Node<T> x = mHead.next; x != mTail; x = x.next) {
            x.data = data;
        }
    }

    @Override
    public boolean insert(T data) {
        linkAfter(data, mTail.pre);
        return true;
    }

    @Override
    public boolean insert(int index, T data) {
        checkIndexForInsert(index);
        if (index == 0) {
            linkAfter(data, mHead);
        } else {
            linkAfter(data, node(index - 1));
        }
        return true;
    }

    @Override
    public boolean insert(int index, T[] data) {
        checkIndexForInsert(index);
        if (data == null) {
            return false;
        }
        if (index == 0) {
            linkAfter(data, mHead);
        } else {
            linkAfter(data, node(index - 1));
        }
        return true;
    }

    @Override
    public boolean insertHead(T data) {
        linkHead(data);
        return true;
    }

    @Override
    public boolean insertTail(T data) {
        linkTail(data);
        return true;
    }

    @Override
    public T delete() {
        return delete(mLength - 1);
    }

    @Override
    public T delete(int index) {
        checkIndex(index);
        return unlink(node(index));
    }

    @Override
    public void delete(int from, int end) {
        checkIndexOfRange(from, end);
        unlink(node(from), end - from + 1);
    }

    @Override
    public boolean delete(Object data) {
        if (data == null) {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (x.data == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<T> x = mHead.next; x != mTail; x = x.next) {
                if (data.equals(x.data)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean deleteFromLast(Object data) {
        if (data == null) {
            for (Node<T> x = mTail.pre; x != mHead; x = x.pre) {
                if (x.data == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<T> x = mTail.pre; x != mHead; x = x.pre) {
                if (data.equals(x.data)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public int deleteAll(Object data) {
        int counts = 0;
        Node<T> curNode = mHead.next;
        Node<T> preNode = mHead;
        if (data == null) {
            while (curNode != mTail) {
                if (curNode.data == null) {
                    unlink(curNode);
                    curNode = preNode.next;
                    counts++;
                } else {
                    preNode = curNode;
                    curNode = curNode.next;
                }
            }
        } else {
            while (curNode != mTail) {
                if (data.equals(curNode.data)) {
                    unlink(curNode);
                    curNode = preNode.next;
                    counts++;
                } else {
                    preNode = curNode;
                    curNode = curNode.next;
                }
            }
        }
        return counts;
    }

    @Override
    public T deleteHead() {
        checkIfElementExists(0);
        return unlinkHead();
    }

    @Override
    public T deleteTail() {
        checkIfElementExists(mLength - 1);
        return unlinkTail();
    }

    @Override
    public boolean isEmpty() {
        return mLength == 0;
    }

    @Override
    public void clear() {
        for (Node<T> x = mHead.next; x != mTail; ) {
            Node<T> next = x.next;
            x.data = null;
            x.pre = null;
            x.next = null;
            x = next;
        }
        mHead.next = mTail;
        mTail.pre = mHead;
        mLength = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[mLength];
        int i = 0;
        for (Node<T> x = mHead.next; x != mTail; x = x.next) {
            array[i++] = x.data;
        }
        return array;
    }

    @Override
    public T[] toArray(Class<T> type) {
        Object copy = Array.newInstance(type, mLength);
        System.arraycopy(toArray(), 0, copy, 0, mLength);
        return (T[]) copy;
    }

    @Override
    public boolean merge(List<T> list) {
        if (list == null) {
            return false;
        }
        Iterator<T> iterator = list.iterator();
        while (iterator.hasNext()) {
            linkAfter(iterator.next(), mTail.pre);
        }
        return true;
    }

    @Override
    public LinkedList<T> subList(int offset, int length) {
        checkLength(length);
        checkIndex(offset);
        LinkedList<T> subList = new LinkedList<>();
        if (length > 0) {
            checkIndex(offset + length - 1);
            Node<T> srcNode = node(offset);
            while (length > 0) {
                subList.linkAfter(srcNode.data, subList.mTail.pre);
                srcNode = srcNode.next;
                length--;
            }
        }
        return subList;
    }

    @Override
    public List<T> subList(int start, int end, int step) {
        checkIndexOfRange(start, end);
        if (step < 1) {
            step = 1;
        }
        if (step == 1) {
            return subList(start, end - start + 1);
        } else {
            LinkedList<T> subList = new LinkedList<>();
            Node<T> curNode = node(start);
            Node<T> endNode = node(end).next;
            while (curNode != endNode) {
                subList.linkTail(curNode.data);
                int k = step;
                while (k > 0 && curNode != endNode) {
                    curNode = curNode.next;
                    k--;
                }
            }
            return subList;
        }
    }

    @Override
    public void reverse() {
        reverse(0, mLength - 1);
    }

    @Override
    public void reverse(int start, int end) {
        checkIndexOfRange(start, end);
        Node<T> startNode = start == 0 ? mHead : node(start - 1);
        Node<T> endNode = startNode.next;
        Node<T> tmp;
        int counts = end - start;
        while (counts > 0) {
            tmp = endNode.next;
            endNode.next = tmp.next;
            startNode.next.pre = tmp;
            tmp.next = startNode.next;
            startNode.next = tmp;
            tmp.pre = startNode;
            counts--;
        }
    }

    @Override
    public void rotate(int k) {
        rotate(0, mLength - 1, k);
    }

    @Override
    public void rotate(int start, int end, int k) {
        if (k >= 0) {
            checkIndexOfRange(start, end);
            int length = end - start + 1;
            k = k % length;
            if (k > 0) {
                Node<T> startNode = start == 0 ? mHead : node(start - 1);
                Node<T> endNode = end == (mLength - 1) ? mTail : node(end + 1);
                Node<T> newStart = node(end + 1 - k);
                endNode.pre.next = startNode.next;
                startNode.next.pre = endNode.pre;
                endNode.pre = newStart.pre;
                startNode.next = newStart;
                endNode.pre.next = endNode;
                newStart.pre = startNode;
            }
        }
    }

    @Override
    public void sort() {
        sort(0, mLength - 1);
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public void sort(int start, int end) {
        Object[] arr = toArray();
        Sort.sort(arr, start, end);
        int index = start;
        for (Node<T> x = node(start); index <= end; x = x.next) {
            x.data = (T) arr[index++];
        }
    }

    @Override
    public void shuffle() {
        shuffle(0, mLength - 1);
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public void shuffle(int start, int end) {
        checkIndexOfRange(start, end);
        if (end > start) {
            Object[] arr = toArray();
            ListOp.shuffle(arr, start, end);
            int index = start;
            for (Node<T> x = node(start); index <= end; x = x.next) {
                x.data = (T) arr[index++];
            }
        }
    }

    protected void linkTail(T data) {
        Node<T> newNode = new Node<>(data, mTail.pre, mTail);
        mTail.pre.next = newNode;
        mTail.pre = newNode;
        mLength++;
    }

    protected void linkHead(T data) {
        Node<T> newNode = new Node<>(data, mHead, mHead.next);
        mHead.next.pre = newNode;
        mHead.next = newNode;
        mLength++;
    }

    protected void linkAfter(T data, Node<T> node) {
        // assert node != null and node != mTail
        Node<T> newNode = new Node<>(data, node, node.next);
        node.next.pre = newNode;
        node.next = newNode;
        mLength++;
    }

    protected void linkAfter(T[] data, Node<T> node) {
        // assert node != null and data != null
        if (data.length == 0) {
            return;
        }
        Node<T> start = new Node<>(data[0], node, null);
        Node<T> current = start;
        for (int i = 1; i < data.length; i++) {
            Node<T> tmp = new Node<>(data[i], current, null);
            current.next = tmp;
            current = tmp;
        }
        current.next = node.next;
        node.next.pre = current;
        node.next = start;
        mLength += data.length;
    }

    protected T unlinkTail() {
        // assert length > 0
        return unlink(mTail.pre);
    }

    protected T unlinkHead() {
        // assert length > 0
        return unlink(mHead.next);
    }

    protected T unlink(Node<T> node) {
        // assert node != null and node != mHead and node != mTail
        T data = node.data;
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.data = null;
        node.pre = null;
        node.next = null;
        mLength--;
        return data;
    }

    protected void unlink(Node<T> start, int counts) {
        // assert node != null and node != mHead and node != mTail
        Node<T> newStart = start.pre;
        int num = 0;
        while (counts > 0 && start != mTail) {
            Node<T> tmp = start.next;
            counts--;
            num++;
            start.pre = null;
            start.next = null;
            start.data = null;
            start = tmp;
        }
        newStart.next = start;
        start.pre = newStart;
        mLength -= num;
    }

    protected void checkIndex(int index) {
        if (index < 0 || index >= mLength) {
            throw new IndexOutOfBoundsException("index: " + index + ", length: " + mLength);
        }
    }

    protected void checkIndexForInsert(int index) {
        if (index < 0 || index > mLength) {
            throw new IndexOutOfBoundsException("index: " + index + ", length: " + mLength);
        }
    }

    protected void checkIndexOfRange(int from, int end) {
        checkIndex(from);
        checkIndex(end);
        if (from > end) {
            throw new IndexOutOfBoundsException("indexes of range are wrong: from: " + from + ", end: " + end);
        }
    }

    protected void checkLength(int length) {
        if (length < 0) {
            throw new InvalidParamException("length is negative: " + length);
        }
    }

    protected void checkIfElementExists(int index) {
        if (index < 0 || index >= mLength) {
            throw new NoSuchElementException("index: " + index + ", list length: " + mLength);
        }
    }

    private Node<T> node(int index) {
        Node<T> x;
        if (index < (mLength >> 1)) {
            x = mHead.next;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        } else {
            x = mTail.pre;
            for (int i = mLength - 1; i > index; i--) {
                x = x.pre;
            }
        }
        return x;
    }

    private static class Node<T> {
        T data;
        Node<T> pre;
        Node<T> next;

        public Node(T data, Node<T> pre, Node<T> next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }
    }

    private class LinkedListIterator implements Iterator<T> {
        Node<T> cursor = mHead.next;
        Node<T> lastReturn = null;
        int index = 0;
        boolean forwardDir = true;

        @Override
        public boolean hasNext() {
            return cursor != mHead && cursor != mTail;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException("cursor: " + index + ", length: " + mLength);
            } else {
                Node<T> node = cursor;
                lastReturn = cursor;
                if (forwardDir) {
                    cursor = cursor.next;
                    index++;
                } else {
                    cursor = cursor.pre;
                    index--;
                }
                return node.data;
            }
        }

        @Override
        public void remove() {
            if (lastReturn == null) {
                throw new IllegalStateException("index of last return element is illegal");
            }
            LinkedList.this.unlink(lastReturn);
            if (forwardDir) {
                index--;
            }
            lastReturn = null;
        }

        @Override
        public int index() {
            return index;
        }

        @Override
        public void reset() {
            cursor = forwardDir ? mHead.next : mTail.pre;
            index = forwardDir ? 0 : mLength - 1;
        }

        @Override
        public void setDirection(boolean reverse) {
            forwardDir = !reverse;
        }
    }
}